package edu.whu.rose.clock.kps.spindex;

public class FloydWarshallAlgorithm {
	
	public static void main(String[] args) {
		int[][] distances = new int[][]{
		{1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0}, 
		{1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0}, 
		{0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0,}, 
		{1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0,}, 
		{0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0,}, 
		{0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0,}, 
		{0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0,}, 
		{0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0,}, 
		{0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0,}, 
		{0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1,}, 
		{0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0,},
		{0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1,}};
		
//		int[][] distances = new int[][]{
//				{0, 3, 8, 0, -4}, 
//				{0, 0, 0, 1, 7}, 
//				{0, 4, 0, 0, 0}, 
//				{2, 0, -5, 0, 0}, 
//				{0, 0, 0, 6, 0}};
		
		int[][] predecessors = new int[distances.length][distances.length];
		for (int i = 0; i < distances.length; i++) {
			for (int j = 0; j < distances.length; j++) {
				if (i == j) {
					distances[i][j] = 0;
				}
				else {
					if (distances[i][j] == 0) {
						distances[i][j] = Integer.MAX_VALUE;
					}
					else {
						predecessors[i][j] = i + 1;
					}
				}
			}
		}
		
		process(distances, predecessors);
		
//		for (int i = 0; i < distances.length; i++) {
//			for (int j = 0; j < distances.length; j++) {
//				System.out.print(distances[i][j] + " ");
//			}
//			System.out.println();
//		}
		for (int i = 0; i < distances.length; i++) {
			for (int j = 0; j < distances.length; j++) {
				System.out.print(predecessors[i][j] + " ");
			}
			System.out.println();
		}
		
		int n = 0;
		int m = 8;
		int k = m;
		System.out.println(distances[n][m]);
		while (k != n) {
			System.out.print(k + " ");
			k = predecessors[n][k] - 1;
		}
	}

	public static void process(int[][] distances, int[][] predecessors) {
		int n = distances.length;
		int[][] matrix1 = distances;
//		int[][] matrix2 = predecessors;
		
//		int[][] temp = new int[n][n];
//		for (int i = 0; i < n; i++) {
//			for (int j = 0; j < n; j++) {
//				if (matrix[i][j] > 0 && matrix[i][j] < Double.MAX_VALUE) {
//					temp[i][j] = 0;
//				}
//			}
//		}
		
		for (int k = 0; k < n; k++) {
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					if (i == j) {
						continue;
					}
					if (matrix1[i][k] != Integer.MAX_VALUE && 
							matrix1[k][j] != Integer.MAX_VALUE &&
							matrix1[i][j] > matrix1[i][k] + matrix1[k][j]) {
						distances[i][j] = matrix1[i][k] + matrix1[k][j];
						predecessors[i][j] = predecessors[k][j];
					}
					else {
						distances[i][j] = matrix1[i][j];
//						predecessors[i][j] = matrix2[i][j];
					}
				}
			}
			matrix1 = distances;
//			matrix2 = predecessors;
		}
	}

}
